class Solution {
    // public int uniquePaths(int m, int n) {
    //     int[][] dp = new int[m][n];
    //     // 将 i==0 和 j==0 的位置全部初始化为1
    //     for (int i = 0; i < n; i++) {
    //         dp[0][i] = 1;
    //     }
    //     for (int i = 0; i < m; i++) {
    //         dp[i][0] = 1;
    //     }
    //     for (int i = 1; i < m; i++) {
    //         for (int j = 1; j < n; j++) {
    //             dp[i][j] = dp[i-1][j] + dp[i][j-1];
    //         }
    //     }
    //     return dp[m-1][n-1];
    // }


    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1; // 将[0,1]位置初始化为1即可
        // 原始的dp表的[0,0]是和新dp表的[1,1]位置相对应的
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}